import java.util.Stack;

public class Order_0316 {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    private static TreeNode createTree () {
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        root.left = node2;
        root.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        return root;
    }

    public static void preOrderNor(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                System.out.print(cur.val + " ");
                cur = cur.left;
            }
            prev = stack.pop();
            cur = prev.right;
        }
    }

    public static void inOrderNor (TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            prev = stack.pop();
            System.out.print(prev.val + " ");
            cur = prev.right;
        }
    }

    public static void postOrder (TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        TreeNode hasprint = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            prev = stack.peek();
            if (prev.right == null || hasprint == prev.right) {
                stack.pop();
                System.out.print(prev.val + " ");
                hasprint = prev;
            } else {
                cur = prev.right;
            }
        }
    }

    public static void main(String[] args) {
        TreeNode root = createTree();
        preOrderNor(root);
        System.out.println();
        inOrderNor(root);
        System.out.println();
        postOrder(root);
    }
}






